Talk:Church-Kleene ordinal
It's pretty unclear for me how to go through all recursive ordinals with this \(\mathcal{O}(n)\). For example, why we pick expression 3*5^10? Why not 4*5^10 or 65*7^63? Also, is O(2^^10) 2^{2^{3 \cdot 5^{10}}}\), but \(2 \uparrow\uparrow 10 <_\mathcal{O} 2^{2^{3 \cdot 5^{10}}}\). :What you are misunderstanding is the purpose of the arithmetic. In this context, \(2^{2^{3 \cdot 5^{10}}}\) is not a numerical value; it's a notation for the successor of the successor of the limit ordinal produced by TM#10. The \(<_\mathcal{O}\) operator couldn't care less about what the values of the numbers really are. FB100Z • talk • 19:14, July 9, 2013 (UTC) ::So it's x+2 where x is the limit ordinal by TM#10. 13:12, January 10, 2018 (UTC) :2,3 and 5 are the smallest primes, but why we need namely primes? Also, what means \(<_\mathcal{O}\)? In the article written that it indicates well-ordering, but what it informally means? Ikosarakt1 (talk ^ ) 19:22, July 9, 2013 (UTC) ::Primes are preferable because they are simple, and via fundamental theorem of arithmetics we can recover exponents if we know result. Also, I hope you heard of non-standard ordering of numbers, for example 1<3<5<...<2<4<6<... with order type w2. Then Kleene's O is such ordering. LittlePeng9 (talk) 19:32, July 9, 2013 (UTC) ::Prime factorization are cool because they let you encode strings of nonnegative integers into just one. On a suspiciously unrelated note, here is a secret message for you guys: 132643162269720193894835002673467678168915246502787883708050635437619042658457896344953125000000000 FB100Z • talk • 20:41, July 9, 2013 (UTC) ::Really curious, what does this mean? Ikosarakt1 (talk ^ ) 17:13, September 4, 2013 (UTC) ::When I first saw that secret message, I was on mobile and I had no way to factorize it. Today I found it again and decoded, revealing message "20 11 1 18 1 19 15 11 9". This should be trivial to decode now. LittlePeng9 (talk) 15:37, May 20, 2014 (UTC) ::I have no idea what this message means. Can you decode it? Ikosarakt1 (talk ^ ) 06:21, June 29, 2014 (UTC) I know that TM's can produce sequences of symbols, not ordinals. So, how to measure limit ordinal or TM#10? Ikosarakt1 (talk ^ ) 17:36, July 11, 2013 (UTC) : Suppose we have a Turing machine which computes some function, e.g. takes input n in unary and outputs f(n) in unary. Let f(n)=2^^n. This machine outputs values \(1,2,2^2,2^{2^2},...\). These numbers represent in Kleene's O numbers \(0,1,2,3,... \), so machine has ordinal which is limit of it, i.e. \(\omega\). If such function f(n) outputed values corresponding to ordinals \(\alpha,\beta,\gamma,...\) then machine computing f would have ordinal corresponding to limit of \(\alpha,\beta,\gamma,...\). LittlePeng9 (talk) 18:35, July 11, 2013 (UTC) : But single TM can compute different functions depending of the form of input. For example, there exists a TM that able to compute 2^n if input is 1_1_1_..._1_1_1 (n 1's) and 2^^n if input is 111...111 (n 1's). Ikosarakt1 (talk ^ ) 18:43, July 11, 2013 (UTC) ::As far as I know, original formulation of O used numbering of recursive functions themselves. In case of machines, we have to choose uniform format of input and output, for example, unary strings. LittlePeng9 (talk) 18:57, July 11, 2013 (UTC) ::Why unary? Why not decimal or at least binary? 15:44, December 3, 2017 (UTC) :::If a TM has only two colors, then when writing in binary, the machine can never know where the input starts and ends. With unary, it's easy to do. LittlePeng9 (talk) 17:49, December 3, 2017 (UTC) :::So this means if a TM has n colors then base n-1 is the largest when the TM knows when input starts and ends. 09:56, January 5, 2018 (UTC) The flaw in my method I found that the problem in my method of constructing \(\omega_1^\text{CK}n\) is the various definitions for fundamental sequences for certain recursive ordinals, leading to different inequalities. So, \(\omega_1^\text{CK}n\) can get a set of definitions rather than one which we probably don't want. Ikosarakt1 (talk ^ ) 08:26, August 9, 2013 (UTC) Enumeration of Turing machines How we exactly enumerate Turing machines? Can anyone present a specific algorithm computing it? Ikosarakt1 (talk ^ ) 10:27, September 4, 2013 (UTC) : Enumeration used in article is completely made up for informal purposes. If you ask for any enumeration, we can take all rule sets valid in Turing machine simulator we use and take them in lexicographical order. LittlePeng9 (talk) 14:45, September 4, 2013 (UTC) :Lexicographical order bases on some alphabet, but how to order TMs like that? I guess that we have to rewrite , and in the line\(a\) as positions\(\lfloor{a \over 3}\rfloor\),\(\lfloor{a \over 3}\rfloor+1\) and\(\lfloor{a \over 3}\rfloor+2\) respectively. Ikosarakt1 (talk ^ ) 16:30, September 4, 2013 (UTC) Yet another question What would happen if the recursive function which specific TM computes can't be expressed in Kleene's O notation? Say, f(n) = 2^^^n+4n^5-2? Do we just ignore this TM? Ikosarakt1 (talk ^ ) 17:11, September 4, 2013 (UTC) :If any of f(0), f(1), etc. doesn't have ordinal value, this machine simply isn't part of Kleene's O. Same if a value is undefined. LittlePeng9 (talk) 19:26, September 4, 2013 (UTC) Question What is the first n for which the computable notation which is capable to define \(\omega_1^\text{CK}n\) is harder than defining \(\omega_1^\text{CK}\) itself? I'm certain that reaching, for example, \(\omega_1^\text{CK}10^{100}\) through computable diagonalization and recursion is impossible even if the entire humanity would spend all its time just to inventing larger and larger recursive diagonalizers and paper to write the entire notation down. Nobody would even be able to verify whether it is well-defined or not. However, defining \(\omega_1^\text{CK}n\) in general, using Turing machines, is fairly easy work. Ikosarakt1 (talk ^ ) 15:04, May 20, 2014 (UTC) Defining \(\omega^\text{CK}_1\) is easy, I don't see what you are really asking for. I can imagine \(\omega^\text{CK}_1200\) already being far above anything we have ever and we will ever define using recursive notations. LittlePeng9 (talk) 15:16, May 20, 2014 (UTC) :But, say,\(\omega_1^\text{CK}4\) must be quite small ordinal (probably even finite) so that defining it will be easier than\(\omega_1^\text{CK}\). So there will be cross point: for some fixed m, reaching\(\omega_1^\text{CK}m\) in the computable way is harder than define\(\omega_1^\text{CK}n\) in general (in non-computable way, of course.) :The light version of this question is related to primitive and non-primitive recursion: What is the first m for which\(f_m(n)\) needs more rules to define than\(f_\omega(n)\)? We can see that\(f_\omega(n)\) requires 4 rules: *\(f_0(n) = n+1\) *\(f_{m+1}(n) = f_m^n(n)\) *\(f_\alpha(n) = f_{\alphan}(n)\) *\(\omegan = n\). While for \(f_4(n)\) we need 5 rules: *\(f_0(n) = n+1\) *\(f_1(n) = f_0^n(n)\) *\(f_2(n) = f_1^n(n)\) *\(f_3(n) = f_2^n(n)\) *\(f_4(n) = f_3^n(n)\) \(f_3(n)\) would need 4 rules, so actually answer m = 4. For \(f_{\omega_1^\text{CK}}(n)\) , it would be much much harder to determine. Ikosarakt1 (talk ^ ) 15:25, May 20, 2014 (UTC) : After we find out what actually is the ordinal we are interested in, then yes, it's really easy to define notation which defines it. But, if you had \(\omega^\text{CK}_115\), then it's practically impossible to completely verify that this ordinal is within range of your notation, even though it might be as small as \(\omega^\omega\). :For the "light version" I don't even want to continue discussion, because of how ambiguous term "rule" is. For example, when defining \(f_{1000}(n)\) why can't we use \(f_0(n)=n+1,f_{m+1}(n)=f^n_m(n)\) and just say that \(f_{1000}\) is a function we look for? This would define FGH up to any fixed level in just 2 rules. LittlePeng9 (talk) 15:44, May 20, 2014 (UTC) ::True, but only when it's finite. Like, for \(f_\omega\), we need 4, but for \(f_\alpha\), we require 2 (iff \(\alpha\) is finite). ::And, \(f_{\omega2}\) requires still 4, BUT, \(f_{\omega^2}\)requires 4, plus \(\omega^2n=\omega n\). So, \(f_{\omega^2}\) is the 1st. ::But if we define \(\omega^2=\omega\omega\), we get \(\omega^n=\omega\cdots\omega\) (with \(n\) omegas), thus we can push it to \(\omega^\omega\), we must define \(\omega^\alphan=\omega^{\alphan}\). 08:10, November 22, 2017 (UTC) Fundamental sequences Let \(N(\alpha)\) be minimal (according to standard ordering of the integers) so that \(\mathcal{O}(N(\alpha)) = \alpha\). I propose that we define the following fundamental sequences for \(\alpha < \): * \(0x = 0\) * \(\alphax = \max\{\beta < \alpha: N(\beta) \leq N(\alpha) + x\}\) I am curious whether this works at all. you're.so. 20:43, June 27, 2014 (UTC) Yes, it looks like that works. Deedlit11 (talk) 06:38, June 28, 2014 (UTC) :I'm fairly sure this is correct, however ordinals can repeat in your fundamental sequences. I don't think it's any problem though. LittlePeng9 (talk) 10:25, June 28, 2014 (UTC) ::It's trivial to modify it to remove the repetitions, although, as you acknowledged, there's not much point in doing that. you're.so. 15:18, June 28, 2014 (UTC) :What's the FS for \(\omega\), using this method? Ikosarakt1 (talk ^ ) 06:24, June 29, 2014 (UTC) :It's uncomputable. LittlePeng9 (talk) 09:03, June 29, 2014 (UTC) :You'll need to find a Turing machine with minimal lexicographical index that returns \(2 \uparrow\uparrow n\) given input \(n\). Letting that index be \(i\), \(\omegax\) is the largest positive integer less than \(3 \cdot 5^i + x\) that can be expressed in the form \(2 \uparrow\uparrow k\). Have fun computing \(i\) and proving that it's minimal. you're.so. 17:06, June 29, 2014 (UTC) I wonder why you have added \(N(\alpha)+\) into your definition. It's valid either way, I believe. LittlePeng9 (talk) 09:05, June 29, 2014 (UTC) :Some background is necessary — this is an almost exact clone of a definition for FS's up to \(\varepsilon_0\) given in Weiermann's "Sometimes slow-growing is fast-growing." The original definition used the "Cichon norm" \(N(\alpha)\), defined recursively as \(N(0) = 0\) and \(N(\alpha) = \max\{n, 1 + \alpha_i\}\) where \(\alpha_i\) are the exponents in the Cantor normal form of \(\alpha\) and \(n\) is the number of exponents in the Cantor normal form. I can't explain the presence of the \(N(\alpha) + \), but I think you're right that it's not necessary. you're.so. 17:06, June 29, 2014 (UTC) THE TRUTH https://sites.google.com/site/aarexnumbers/aarexinf it's vel 16:17, October 15, 2014 (UTC) : yes LittlePeng9 (talk) 16:37, October 15, 2014 (UTC) : What?What was on that page?Boboris02 (talk) 09:15, March 26, 2017 (UTC) ::Typical Aarex stuff. LittlePeng9 (talk) 09:33, March 26, 2017 (UTC) ::There is no way Aarex wrote that.Boboris02 (talk) 09:44, March 26, 2017 (UTC) :::He did a few years ago. LittlePeng9 (talk) 09:49, March 26, 2017 (UTC) Questions from which I can deduce others Is the Church-Kleene Fixed Point uncountable? If so, what's its value? Is there a notation other than \(\omega_{\omega_{\cdot_{\cdot_\cdot}}^\text{CK}}^\text{CK}\)? (like \(\text{Fix}_1^\text{CK}\)) 17:49, November 17, 2017 (UTC) :It's countable and there is no standard notation for it. LittlePeng9 (talk) 11:38, November 15, 2017 (UTC) ::I will let \(\varphi^\text{CK}(1,\alpha)\) the Church-Kleene fixed points. ::Is the First Church-Kleene Fixed Point \(<\Sigma\)? :: 10:56, November 30, 2017 (UTC) :::Yes, this fixed point is smaller than \(\Sigma\). In fact, it's much smaller than \(\zeta\). LittlePeng9 (talk) 17:49, December 3, 2017 (UTC) ::::Then, use \(\vartheta^\text{CK}(\Omega^x)\) to denote CK fixed point hierarchy's fixed points. ::::Then, is \(\vartheta^\text{CK}(\varepsilon_{\Omega+1})<\lambda?\) 10:01, January 5, 2018 (UTC) Fixed points Is \(\omega^{\text{CK}}_1\) an epsilon number? A zeta number? A fixed point of zeta numbers? A gamma number? And a fixed point of gamma numbers? Is \(\theta(\Omega^\Omega,\omega^{\text{CK}}_1)=\omega^{\text{CK}}_1\)? What about \(\theta(\Omega^{\Omega^\Omega},\omega^{\text{CK}}_1)\), \(\theta(\Omega_2,\omega^{\text{CK}}_1)\), \(\theta(\Omega_\omega,\omega^{\text{CK}}_1)\), \(\theta(\psi_I(0),\omega^{\text{CK}}_1)\), and so on? Why? {hyp/^,cos} (talk) 05:10, January 22, 2018 (UTC) :One way to show that \(\omega^{\text{CK}}_1\) is a fixed point of a normal ordinal function \(f\) is to construct of constructive system of notation for \(f(\alpha)\), given a constructive system of notation for \(\alpha\). :By a constructive system of notation for \(\alpha\), we mean the following things: :There is a function \(v\) from the integers onto \(\alpha\). :There is a partial recursive function \(k: \mathbb{N} \to \{ 0,1,2 \} \) such that \(k(n)\) is 0, 1, or 2 depending on whether \(v(n)\) is 0, successor, or limit. :There is a partial recursive function \(p:\mathbb{N} \to \mathbb{N}\) such that, whenever \(v(n)\) is a successor ordinal, \(v(n) = v(p(n)) + 1\). :There is a partial recursive function \(q:\mathbb{N} \to \mathbb{N}\) such that, whenever \(v(n)\) is a limit ordinal, then the \(q(n)\)th partial recursive function \(\phi_{q(n)}\) (under some canonical ordering of all partial recursive functions) is a total function that represents an increasing sequence of ordinals whose limit is \(v(n)\). :Now, it has been proven that the ordinals for which there exists a constructive system of notation are precisely the ordinals up to and including \(\omega^{\text{CK}}_1\). (In fact one could take this as the definition of \(\omega^{\text{CK}}_1\), and later prove that \(\omega^{\text{CK}}_1\) is the first nonrecursive ordinal.) So if \(\omega^{\text{CK}}_1\) is not a fixed point of \(f\), then \(f(\omega^{\text{CK}}_1) > \omega^{\text{CK}}_1\), so if one could make a constructive system of notation for \(f(\omega^{\text{CK}}_1)\), there would be a contradiction. :So, if we let \(f(\alpha) = \omega^\alpha\), we want to construct a system of notation for \(\omega^\alpha\) given one for \(\alpha\). The obvious thing to use here is Cantor Normal Form; every ordinal \(\beta\) can be represented as: :\(\beta = \omega^{\beta_1} + \ldots + \omega^{\beta_n}\) :Now, it's not hard to construct a computable bijection between \(\mathbb{N}\) and the set of finite sequences of natural numbers. So, given a function \(v\) from the natural numbers onto \(\alpha\), we can construct a function from the natural numbers onto \(\omega^\alpha\) as follows: given a natural number \(n\), we use the previous bijection to get a finite sequence of natural numbers \(n_1, n_2, \ldots, n_m\), and then we set \(v_2(n) = \omega^{v(n_1)} + \ldots + \omega^{v(n_m)}\). It's easy to identify whether \(v_2(n)\) is zero, a successor ordinal, or a limit ordinal, and also easy to find the predecessor ordinal of a successor ordinal. So, it remains to find a partial recursive function that gives the fundamental sequences for limit ordinals. The limit ordinals will be those \(v_2(n)\) for which \(v(n_m)\) will be greater than 0, and in that case, we do the following to find the ith element of the fundamental sequence of \(v_2(n)\): :If \(v(n_m)\) is a successor ordinal, than we find its predecessor (which we know is a computable operation), and replace \(n_m\) with i copies of its predecessor in the finite sequence of natural numbers. Then take the inverse bijection to turn the finite sequence into a single natural number. :If \(v(n_m)\) is a limit ordinal, we replace \(n_m\) with \(\phi_{q(n_m)}(i)\), i.e. we replace the limit ordinal with the ith element of its fundamental sequence. :So we do indeed have a constructive system of notation. So \(\omega^{\text{CK}}_1\) is a fixed point of \(\alpha \mapsto \omega^\alpha\), i.e. it is an epsilon-number. :Challenge: Try to answer your following questions using the method above. Deedlit11 (talk) 08:32, January 22, 2018 (UTC) Example May I add this to the article? Are the following statements correct? Say that we want to compute ωn. Then it's fundamental sequence is O(fiω(n)), and iω is the set of finite numbers (indices) i so that O(i) = ω. These are indices of Turing machines in form i = 3*5j. Say that, for some ordering, Turing machines with indexes 1000,10000,100000 etc. compute 2↑↑n. We find that iω = 1000. Then ωn = O(f1000(n)) = n. Triakula (talk) 07:48, January 17, 2020 (UTC) : Your explanation seems to have typos or incorrect arguments. Since f_A(n) is not necessarily defined for a set A of indices, f_{i_ω}(n) does not make sense in your convention. In the article, i_ω is not a set of indices, but is the minimum of such a set. For example, if i_ω = 1000 and the TM with index 1000 computes 2↑↑n, then ωn = O(f_1000(n)) = O(2↑↑n) = 1+n. If i_ω = 11111 and the TM with index 11111 computes 2↑↑↑n, then ωn = O(f_11111(n)) = O(2↑↑↑n) = (1 if n=0, and 1+(2↑↑↑(n-1)) if n>0). : p-adic 10:13, January 17, 2020 (UTC) ::Thank you. There was a typo about iω. Triakula (talk) 10:25, January 17, 2020 (UTC) ::: Also, n seems to be a typo of 1+n. ::: p-adic 10:47, January 17, 2020 (UTC) ::::Yes. Triakula (talk) 10:55, January 17, 2020 (UTC) I also wanted to add information about that certainly, under this definition, ω1CK0 = 0, ω1CK1 = 1 and ω1CK2 = 2, since ω1CK0 = 0 by definition and 1 with 2 can't be expressed in the form 3*5n. For ω1CK3 we can't be sure though as 3 = 3*50. Triakula (talk) 10:55, January 17, 2020 (UTC) : I agree that those examples (and the dependency of 3 on the actual enumeration of TMs) are good. : p-adic 12:56, January 17, 2020 (UTC) Outgrowing fω Am I correct that regardless of the ordering of TMs, fω1CK >* fω in the Wainer hierarchy because the fundamental sequence of ω1CK is increasing? Triakula (talk) 09:19, January 30, 2020 (UTC) : If we can choose a system of fundamental sequences up to ω_1^{CK}, then perhaps fω1CK = fω can happen, although I do not have an explicit example. If we restrict it to the case whether the system is given by Kleene's O with respect to a certain enumeration, then I am not certain. : p-adic 22:39, February 6, 2020 (UTC) Outgrowing Σ Is it correct that under some ordering there might be a recursive ordinal α so that fα(n) >* Σ(n)? Triakula (talk) 19:28, February 6, 2020 (UTC) : I guess that it is true, but I am not certain. : p-adic 22:39, February 6, 2020 (UTC)